package main

import (
	"fmt"
	"math"
)

// 暴力法 超出时间限制
/*
func nthUglyNumber(n int) int {
	i := 1
	count := 0
	res := 1
	for {
		result := ugly(i)
		if result{
			count += 1
			res = i
		}
		if count == n{
			break
		}
		i += 1
	}
	return res
}

func ugly(num int) bool {
	if num < 1{
		return false
	}
	for num != 1{
		if num % 2 == 0{
			num /= 2
		}else if num%3==0 {
			num /=3
		} else if num%5==0 {
			num /=5
		} else {
			return false
		}
	}
	return num == 1
}
*/

// 动态规划
func nthUglyNumber(n int) int {
	nums := []int{1}
	i2, i3, i5 := 0, 0, 0
	for i := 1; i < n; i++ {
		uglyNum := int(math.Min(math.Min(float64(nums[i2]*2), float64(nums[i3]*3)), float64(nums[i5]*5)))
		nums = append(nums, uglyNum)
		if uglyNum == nums[i2]*2 {
			i2++
		}
		if uglyNum == nums[i3]*3 {
			i3++
		}
		if uglyNum == nums[i5]*5 {
			i5++
		}
	}
	return nums[n-1]
}

func main() {
	res := nthUglyNumber(10)
	fmt.Println(res)
}
